[题解]BJOI2019删数

发表于 更新于 阅读次数：

这道题算是再次更新了我对线段树的认知，果然别人家的线段树什么都能干。

题意：给定一个长度为n的序列，每次删除值为当前序列长度的元素，你可以改变一些元素的val使经过若干次删除后序列为空，求最少改变次数。

ps：另有m次操作，每次改变一个元素的值或者使全部元素+1/-1，操作完之后再次询问最少改变次数。

Solution

首先明白这个游戏怎么玩。

显然序列的顺序可以随便换，我们把它们丢进一个桶中，一个序列是可以被删完，当且仅当每个下标为a_i的点右边有一个下标为x的桶里装了k个元素，且a>=x-k+1。

题解中有一个形象的解释：把每个元素落在它val的柱子上，每落一次高度加一，推到所有柱子，刚好覆盖所有1~n个点。

思考不带修改怎么做，就是暴力推完柱子看有几个还没有被覆盖，空位数即答案。

为什么这是对的？

1.每次最多填补一个空位,这是显然的，即便你不是“搬运”而是直接“添加”，每次也只能填一个，所以空位数就是最优解。

2.对于每个空位，只需要找到一个被“重复覆盖”的点，把它搬到这个空位上即可。也就是说我们至少可以找到一组最优解。

那么带修怎么做呢？

第一问简直是弟弟，考试的时候我的办法是，开一个cnt记录真实的桶里每个val有多少个，每次cnt[val]=0->cnt[val]=1就++ans，反之--ans即可。

第二问考场上fake了。显然是不能直接暴力全部+1的，可以用个线段树维护一下，开始把树扔在中间，然后每次平移查询的区间即可。

但是很重要的一点，移出去的柱子是不在计算贡献的。就是说一个柱子不在现在的1~n中，它就不能再“推到覆盖”那些点了，因为它自己这cnt个要花费cnt个代价移动进来，所以要把这个柱子覆盖的这些点的“被覆盖次数”-1，反之当区间右移的时候要更新那个新加入的柱子的贡献，也就是区间+1。

然而我native的只做了平移，于是考试就只有60pts了。

那么我们现在要干什么呢？

找到一种数据结构，支持区间加减，询问区间=0的个数。

于是线段树就出场了，事实上它可以维护区间最小值的个数，此题中只要在query的时候只加上Min=0的sum即可。

维护两个东西:Min区间最小值 Sum区间最小值出现的次数。

另外加上维护区间加减必须的加减懒标记即可。

每次up的时候如果Minls!=Minrs那么直接继承较小那边的信息，否则就直接把两个并起来。

pushdown的时候因为区间加减不会改变区间最小值的个数,所以pushdown只修改一个Min然后下传标记即可。

然后这道题就愉快的做完了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
static char buf[100000],*pa,*pd;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read(){
 	register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=710000,limit=700000;
int L=360000,R,siz[N],cnt[N],n,m,sum[N<<2],Min[N<<2],tag,a[N],sumtag[N<<2];
#define ls id<<1
#define rs id<<1|1
#define mid ((l+r)>>1)
//Min 最小值 sum最小值出现次数 
void up(int id){
 	if(Min[ls]<Min[rs])Min[id]=Min[ls],sum[id]=sum[ls];
    else if(Min[ls]>Min[rs])Min[id]=Min[rs],sum[id]=sum[rs];
    else Min[id]=Min[ls],sum[id]=sum[ls]+sum[rs]; 
}  
void pushdown(int id){
    sumtag[ls]+=sumtag[id];
    sumtag[rs]+=sumtag[id];
    Min[ls]+=sumtag[id];
    Min[rs]+=sumtag[id];
    sumtag[id]=0; 
}
void build(int l,int r,int id){
 	if(l==r){
     	sum[id]=1;
     	Min[id]=siz[l];
        return;
    } 
    build(l,mid,ls);
    build(mid+1,r,rs);
    up(id);
} 
void add(int l,int r,int x,int y,int z,int id){
 	if(l>=x&&r<=y){
     	Min[id]+=z;
     	sumtag[id]+=z; 
        return;
    }
    pushdown(id); 
    if(x<=mid)add(l,mid,x,y,z,ls);
    if(y>mid) add(mid+1,r,x,y,z,rs);
    up(id);
} 
int query(int l,int r,int x,int y,int id){
 	if(l>=x&&r<=y){
 		if(!Min[id])return sum[id];
        else return 0;	
    }
    int ans=0;
    pushdown(id);
    if(x<=mid)ans+=query(l,mid,x,y,ls);
    if(y>mid)ans+=query(mid+1,r,x,y,rs);
    return ans;
} 

int main(){
//	freopen("data26.in","r",stdin);
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
 	n=read();m=read();
    R=L+n-1;
    register int i,j;
    for(i=1;i<=n;i++)a[i]=read(),cnt[L+a[i]-1]++;
    for(i=L;i<=R;i++)
        for(j=1;j<=cnt[i];j++)	
            siz[i-j+1]++;
    build(1,limit,1);
    for(i=1;i<=m;i++){
        int opt=read(),x=read();	
        if(opt==0){
            L-=x;R-=x;
            tag+=x;
            if(x==1){
                if(cnt[R+1])
                add(1,limit,R+1-cnt[R+1]+1,R+1,-1,1);
            }
            else{
                if(cnt[R])
                add(1,limit,R-cnt[R]+1,R,1,1);
            }
        } 
        else{
            if(L+a[opt]+tag-1<=R)
            add(1,limit,L+a[opt]+tag-cnt[L+a[opt]+tag-1],L+a[opt]+tag-cnt[L+a[opt]+tag-1],-1,1);
            cnt[L+a[opt]+tag-1]--;
            a[opt]=x-tag;
            cnt[L+a[opt]+tag-1]++;
            if(L+a[opt]+tag-1<=R)
            add(1,limit,L+a[opt]+tag-cnt[L+a[opt]+tag-1],L+a[opt]+tag-cnt[L+a[opt]+tag-1],1,1);	
        }
//		for(j=L;j<=R;j++)cout<<siz[j]<<' ';
//		cout<<'\n';
    //	cout<<L<<' '<<R<<'\n';
        cout<<query(1,limit,L,R,1)<<'\n';
    } 
}
0%